package site.wanjiahao.back_tracking;

/**
 * N皇后问题
 * 使用回溯＋剪枝处理
 */
public class Queens2 {

    // 标记某一列是否有换后
    private boolean cols[];

    // 标记左上斜对角线
    private boolean leftTop[];

    // 标记右上斜对角线
    private boolean rightTop[];

    private int ways;

    public Queens2(int size) {
        if (size <= 1) return;
        cols = new boolean[size];
        int len = (size << 1) - 1;
        leftTop = new boolean[len];
        rightTop = new boolean[len];
    }

    // 摆放皇后
    public void place() {
        // 从第一个元素开始摆放
        place(0);
        System.out.println("共有" + ways + "种摆法");
    }

    public void place(int row) {
        // 确定递归基
        if (row >= cols.length) {
            // 成功确定一次摆放位置
            ways++;
            // 展示当前摆放，详情
            return;
        }
        // 遍历列，确定那个位置摆放皇后
        for (int col = 0; col < cols.length; col++) {
            // 列不能摆放
            if (cols[col]) continue;
            // 对角线不能摆放
            int ltIndex = row - col + cols.length - 1;
            if (leftTop[ltIndex]) continue;
            int rtIndex = row + col;
            if (rightTop[rtIndex]) continue;

            cols[col] = true;
            leftTop[ltIndex] = true;
            rightTop[rtIndex] = true;
            // 递归调用下一个元素摆放，当此函数弹出，将会自动执行回溯操作
            place(row + 1);
            cols[col] = false;
            leftTop[ltIndex] = false;
            rightTop[rtIndex] = false;
        }
    }

    /*private void show() {
        int len = cols.length;
        for (int col : cols) {
            for (int j = 0; j < len; j++) {
                if (col == j) {
                    System.out.print("1 ");
                } else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println("--------------------------");
    }*/

}
